package code.oldCode.classic150;

import java.util.*;

/**
 * @author cuihaoran
 * @date 2025/1/17
 */
public class Classic150_backtracking {

    /* 17. 电话号码的字母组合 */
    public List<String> letterCombinations(String digits) {
        Map<Character, char[]> map = new HashMap<>();
        map.put('2', new char[]{'a', 'b', 'c'});
        map.put('3', new char[]{'d', 'e', 'f'});
        map.put('4', new char[]{'g', 'h', 'i'});
        map.put('5', new char[]{'j', 'k', 'l'});
        map.put('6', new char[]{'m', 'n', 'o'});
        map.put('7', new char[]{'p', 'q', 'r', 's'});
        map.put('8', new char[]{'t', 'u', 'v'});
        map.put('9', new char[]{'w', 'x', 'y', 'z'});
        List<String> ans = new ArrayList<>();
        char[] chars = digits.toCharArray();
        letterDFS(chars, 0, ans, new StringBuilder(), map);
        return ans;
    }

    private void letterDFS(char[] chars, int index, List<String> ans, StringBuilder sb, Map<Character, char[]> map) {
        if (index == chars.length) {
            if (sb.length() > 0)
                ans.add(sb.toString());
            return;
        }
        char[] nextChars = map.get(chars[index]);
        for (char nextChar : nextChars) {
            sb.append(nextChar);
            letterDFS(chars, index + 1, ans, sb, map);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    /* 77. 组合 */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> lists = new ArrayList<>();
        combineDFS(1, lists, new ArrayList<>(), k, n);
        return lists;
    }

    private void combineDFS(int index, List<List<Integer>> lists, List<Integer> list, int k, int n) {
        int listSize = list.size();
        // 如果加满了，添加list到lists
        if (listSize == k) {
            lists.add(new ArrayList<>(list));
            return;
        }
        // 剪枝，如果当前list中最后一个值的大小使剩余容量超过了n，返回
        if (listSize > 0 && list.get(listSize - 1) + (k - listSize) > n)
            return;
        // DFS
        for (int i = index; i <= n; i++) {
            list.add(i);
            combineDFS(i + 1, lists, list, k, n);
            list.remove(list.size() - 1);
        }
    }

    /* 46. 全排列 */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        int len = nums.length;
        permuteDFS(lists, new ArrayList<>(), nums, new boolean[len]);
        return lists;
    }

    private void permuteDFS(List<List<Integer>> lists, List<Integer> list, int[] nums, boolean[] isVisited) {
        int len = nums.length;
        if (list.size() == len) {
            lists.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                list.add(nums[i]);
                permuteDFS(lists, list, nums, isVisited);
                list.remove(list.size() - 1);
                isVisited[i] = false;
            }
        }
    }

    /* 39. 组合总和 */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(candidates);
        combinationSumDFS(candidates, target, lists, new ArrayList<>(), 0, 0);
        return lists;
    }

    private void combinationSumDFS(int[] candidates, int target, List<List<Integer>> lists, List<Integer> list, int sum, int index) {
        if (sum == target) {
            lists.add(new ArrayList<>(list));
        }
        if (sum > target) {
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            list.add(candidates[i]);
            sum += candidates[i];
            combinationSumDFS(candidates, target, lists, list, sum, i);
            sum -= candidates[i];
            list.remove(list.size() - 1);
        }
    }

    /* 22. 括号生成 */
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        generateParenthesisBT(list, new StringBuilder(), 0, 0, n);
        return list;
    }

    void generateParenthesisBT(List<String> list, StringBuilder sb, int leftBrackets, int rightBrackets, int n) {
        if (sb.length() == 2 * n) {
            list.add(new String(sb));
            return;
        }
        // 可以选择左括号的情况：左括号数量小于n
        if (leftBrackets < n) {
            sb.append('(');
            generateParenthesisBT(list, sb, leftBrackets + 1, rightBrackets, n);
            sb.deleteCharAt(sb.length() - 1);
        }
        // 可以选择右括号的情况：左括号数量大于右括号
        if (rightBrackets < leftBrackets) {
            sb.append(')');
            generateParenthesisBT(list, sb, leftBrackets, rightBrackets + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    /* 79. 单词搜索 */
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        char[] w = word.toCharArray();
        boolean[][] isVisited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                isVisited[i][j] = true;
                if (existDFS(board, w, m, n, isVisited, i, j, 0))
                    return true;
                isVisited[i][j] = false;
            }
        }
        return false;
    }

    boolean existDFS(char[][] board, char[] word, int m, int n, boolean[][] isVisited, int i, int j, int pos) {
        if (pos >= word.length || word[pos] != board[i][j])
            return false;
        if (pos == word.length - 1)
            return true;

        boolean ans = false;
        // ↑
        if (i - 1 >= 0 && !isVisited[i - 1][j]) {
            isVisited[i - 1][j] = true;
            ans = existDFS(board, word, m, n, isVisited, i - 1, j, pos + 1);
            isVisited[i - 1][j] = false;
        }
        // ↓
        if (i + 1 < m && !isVisited[i + 1][j]) {
            isVisited[i + 1][j] = true;
            ans = ans || existDFS(board, word, m, n, isVisited, i + 1, j, pos + 1);
            isVisited[i + 1][j] = false;
        }
        // ←
        if (j - 1 >= 0 && !isVisited[i][j - 1]) {
            isVisited[i][j - 1] = true;
            ans = ans || existDFS(board, word, m, n, isVisited, i, j - 1, pos + 1);
            isVisited[i][j - 1] = false;
        }
        // →
        if (j + 1 < n && !isVisited[i][j + 1]) {
            isVisited[i][j + 1] = true;
            ans = ans || existDFS(board, word, m, n, isVisited, i, j + 1, pos + 1);
            isVisited[i][j + 1] = false;
        }
        return ans;
    }

    public static void main(String[] args) {
        Classic150_backtracking c = new Classic150_backtracking();
        System.out.println(c.combine(4, 2));
    }
}
